﻿namespace Leetcode.N0719;

public class Solution
{
    public int SmallestDistancePair(int[] nums, int k)
    {
        nums = nums.OrderBy(_ => _).ToArray();
        int lo = 0;
        int hi = nums[nums.Length - 1] - nums[0];

        while (lo < hi)
        {
            int mi = (lo + hi) / 2;
            int count = 0, left = 0;

            for (int right = 1; right < nums.Length; ++right)
            {
                while (nums[right] - nums[left] > mi)
                {
                    left++;
                }
                count += right - left;
            }

            if (count >= k)
            {
                hi = mi;
            }
            else
            {
                lo = mi + 1;
            }
        }
        return lo;
    }
}
